package leetcode;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public int len() {
        int len = 0;
        ListNode thisNode = this;
        while (thisNode.next != null) {
            len ++;
            thisNode = thisNode.next;
        }
        return len;
    }
}

public class LeetCode02 {
//    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        ListNode head = null, tail = null;
//        int carry = 0;
//        while (l1 != null || l2 != null) {
//            int v1 = l1 == null ? 0 : l1.val;
//            int v2 = l2 == null ? 0 : l2.val;
//            int sum = v1 + v2 + carry;
//            if (head == null) {
//                head = tail = new ListNode(sum % 10);
//            } else {
//                tail.next = new ListNode(sum % 10);
//                tail = tail.next;
//            }
//            carry = sum / 10;
//            if (l1 != null) {
//                l1 = l1.next;
//            }
//            if (l2 != null) {
//                l2 = l2.next;
//            }
//        }
//        if (carry > 0) {
//            tail.next = new ListNode(carry);
//        }
//        return head;
//    }

    public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            int sum = v1 + v2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry > 0) tail.next = new ListNode(carry);
        return head;
    }

    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode longNode = l1.len() >= l2.len() ? l1 : l2;
        ListNode shortNode = longNode == l1 ? l2 : l1;
        ListNode resultNode = longNode;
        ListNode last = null;
        int carry = 0;
        // 1，短的和长的都不为空
        while (shortNode != null) {
            int sum = longNode.val + shortNode.val + carry;
            longNode.val = sum % 10;
            carry = sum / 10;
            last = longNode;
            longNode = longNode.next;
            shortNode = shortNode.next;
        }
        // 2，长的不为空，短的为空
        while (longNode != null) {
            int sum = longNode.val + carry;
            longNode.val = sum % 10;
            carry = sum / 10;
            last = longNode;
            longNode = longNode.next;
        }
        if (carry == 1) {
            last.next = new ListNode(1);
        }
        return resultNode;
    }

    public static void main(String[] args) {
        ListNode d1 = new ListNode(2);
        d1.next = new ListNode(4);
        d1.next.next = new ListNode(3);
        d1.next.next.next = new ListNode(4);

//        System.out.println("d1.len() = " + d1.len());

        ListNode d2 = new ListNode(5);
        d2.next = new ListNode(6);
        d2.next.next = new ListNode(4);

//        System.out.println("d2.len() = " + d2.len());

        ListNode ret = addTwoNumbers1(d1, d2);
        while (ret != null) {
            System.out.print(" " + ret.val);
            ret = ret.next;
        }
        System.out.println();

        ListNode ret1 = addTwoNumbers2(d1, d2);
        while (ret1 != null) {
            System.out.print(" " + ret1.val);
            ret1 = ret1.next;
        }
    }
}
